package FourthWeek;

public class Tuesday {
    //81、搜索旋转排序数组
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target ? true : false;
        }
        int left = 0,right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[left] == nums[mid] && nums[right] == nums[mid]) {
                //因为可能出现这种情况 ：[2,1,2,2,2,2,2]，使得left = mid = right的值
                //无法判断哪段是有序的哪段是无序的，所以我们进行left++，right--，规避掉这种
                left++;
                right--;
            }else if (nums[left] <= nums[mid]) {
                //有序的一段，在有序的一段区间里面去寻找
                if (target < nums[mid] && nums[left] <= target) {
                    //nums[0] <= target是为了保证 target这个数据是在有序的这一段中，如果不存在就去无序中寻找
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }else {
                if (target > nums[mid] && nums[n - 1] >= target) {
                    //nums[n - 1] >= target是为了保证 target这个数据是在无序的这一段中，如果不存在就去有序中寻找
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }

    //74、搜索二维矩阵
    public static boolean searchMatrix1(int[][] matrix, int target) {
        //暴力枚举
        int m = matrix.length;
        int n = matrix[0].length;

        for (int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] arrays = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 60;
        System.out.println(searchMatrix1(arrays, target));
    }


    public boolean searchMatrix(int[][] matrix, int target) {
        //我们对于这个二维数组分成二次二分查找去解决

        //第一次：寻找 target 这个数据在二维数组的哪一行中，可以分成两段
        //对于第一列的数据来说分为: matrix[mid][0] <= target  left = mid
        //                      matrix[mid][0] > target right = mid - 1
        int row = searchMatrixRow(matrix,target);
        //判断这个row是否存在
        if (row < 0) {
            return false;
        }

        //对于第二次二分查找，当找到target这个数据可能存在在找到的那一行中，进行二分,加入是第row这行
        // matrix[row][mid] <= target  left = mid
        // matrix[row][mid] > target right = mid - 1
        boolean ret = searchTarget(matrix[row],target);
        return ret;
    }

    private int searchMatrixRow(int[][] matrix, int target) {
        int left = 0,right = matrix.length - 1;//二维数组中的每一个一维数组就是一个长度
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if (matrix[mid][0] <= target) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean searchTarget(int[] matrix, int target) {
        int left = 0,right = matrix.length - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if (matrix[mid] <= target) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        if (left >= 0 && left < matrix.length && matrix[left] == target) {
            return true;
        }else {
            return false;
        }
    }
}
